# Author    :Dun_Hz
# Time      :2024/7/26 15:04
# 快速排序，左右两个指针，p元素左边都比它小，右边都比它大

def partition(li,left,right):
    tmp=li[left]
    while left<right:
        while li[right]>tmp and left<right:
            right-=1
        # 退出循环的情况：left和right指针遇上或者找到了比tmp小的数
        # 如果遇到了比tmp小的数，移过去
        # 如果相遇了，说明右边都比tmp大
        li[left]=li[right]
        while li[left]<tmp and left<right:
            left+=1
        li[right]=li[left]
    li[left]=tmp
    return left

def quick_sort(li,left,right):
    if left<right:  #至少有两个元素，才能排序
        mid=partition(li,left,right)
        quick_sort(li,left,mid-1)
        quick_sort(li,mid+1,right)

if __name__=="__main__":
    li=[6,4,2,1,5,3,8,7,9]
    quick_sort(li,0,len(li)-1)
    print(li)


